Turing completo

En la teoría de computadoras reales y virtuales, de los lenguajes de programación y de otros sistemas lógicos, un sistema Turing completo es aquel que tiene un poder computacional equivalente a la máquina de Turing universal. En otras palabras, el sistema y la máquina universal de Turing pueden emularse entre sí.

Aun cuando es físicamente imposible que existan estas máquinas debido a que requieren de almacenamiento ilimitado y probabilidad cero de falla, de forma coloquial la completitud de Turing se atribuye a máquinas físicas o lenguajes de programación que podrían ser universales si tuvieran almacenamiento infinito y fueran absolutamente fiables. La primera de esas máquinas apareció en 1941: la Z3 de Konrad Zuse, que era controlada por programas. Su universalidad, sin embargo, fue demostrada mucho después por Raúl Rojas en 1998.^[1]​ En ese sentido laxo, todas las computadoras modernas son también Turing completas.

La completitud de Turing es significativa, pues, cada diseño verosímil de un dispositivo de computación, por más avanzado que sea (aun las computadoras cuánticas), pueden ser emuladas por una máquina universal de Turing. Así, una máquina que pueda actuar como una máquina universal de Turing puede, en principio, hacer cualquier cálculo que cualquier otra computadora es capaz de hacer (ver Tesis de Church-Turing). Obsérvese, sin embargo, que no dice nada sobre el esfuerzo de escribir un programa para la máquina o sobre el tiempo que puede tomar el cálculo.

Está la hipótesis de que el Universo es Turing completo (ver implicaciones filosóficas en la Tesis de Church-Turing y en Física digital).

Ver el artículo en Teoría de la computabilidad para una larga lista de sistemas que son Turing completos, así como varios sistemas que son menos poderosos, y varios sistemas teóricos que serían aún más poderosos que la máquina universal de Turing.

1. ↑ Link a paper (en ingles)